/*
 * poly.cpp
 *
 *  Created on: 2010-12-1
 *      Author: samuel
 */
#include "../include/list.h"
#include "assert.h"
#include "stdlib.h"
#include "stdio.h"
#include "string.h"


struct ArrayNode
{
    int coeff[MAX_EXPONENT + 1];
    int power;
};


#define MAX_POWER(a, b) ((a) > (b) ? (a) : (b))


ArrayPoly MakeArrayPoly(int max_exponent)
{
    ArrayPoly p = (ArrayPoly)malloc(sizeof(ArrayNode));
    if (p != 0)
    {
        for (int i = 0; i <= max_exponent; i++)
        {
            p->coeff[i] = (rand()/(RAND_MAX + 1.0)) * 10;
        }
        p->power = max_exponent;
    }

    return p;
}

void DestoryArrayPoly(ArrayPoly p)
{
    assert(p != 0);

    free(p);
}

void PrintArrayPoly(const ArrayPoly p)
{
    assert (p != 0);
    int i;

    printf("\n%d + ", p->coeff[0]);
    for (i = 1; i < p->power; i++)
    {
        printf("%dx(%d) + ", p->coeff[i], i);
    }
    printf("%dx(%d)", p->coeff[i], i);
}

ArrayPoly AddArrayPoly(const ArrayPoly p1, const ArrayPoly p2)
{
    assert(p1 != 0 && p2 != 0);

    ArrayPoly sum = (ArrayPoly)malloc(sizeof(ArrayNode));
    if (sum != 0)
    {
        sum->power = MAX_POWER(p1->power, p2->power);
        for (int i = 0; i <= sum->power; i++)
        {
            sum->coeff[i] = p1->coeff[i] + p2->coeff[i];
        }
    }

    return sum;
}

ArrayPoly MultiArrayPoly(const ArrayPoly p1, const ArrayPoly p2)
{
    assert(p1 != 0 && p2 != 0);

    ArrayPoly multi = (ArrayPoly)malloc(sizeof(ArrayNode));
    if (multi != 0)
    {
        memset(multi, 0x00, sizeof(ArrayNode));
        multi->power = p1->power + p2->power;
        for (int i = 0; i <= p1->power; i++)
        {
            for (int j = 0; j <= p2->power; j++)
            {
                multi->coeff[i + j] += p1->coeff[i] * p2->coeff[j];
            }
        }
    }

    return multi;
}


struct ListNode
{
    int coeff, expo;
    struct ListNode *next;
} ;


static ListNode* MakeListNode(int coeff, int exponent);
static ListNode* SetNodeValue(ListNode *node, int coeff, int exponent);
static void AppendNodeInSort(ListPoly poly, const ListNode *node);

static ListNode* MakeListNode(int coeff, int exponent)
{
    ListNode *p = (ListNode *)malloc(sizeof(sizeof(ListNode)));

    if (p)
    {
        p->coeff = coeff;
        p->expo = exponent;
        p->next = 0;
    }

    return p;
}

static ListNode* SetNodeValue(ListNode *node, int coeff, int exponent)
{
	assert(node != 0);

	node->coeff = coeff;
	node->expo = exponent;

	return node;
}

static void AppendNodeInSort(ListPoly poly, const ListNode *node)
{
	assert(poly != 0 && node != 0);

	while (poly->next && (poly->next->expo != node->expo))
	{
		poly = poly->next;
	}

	if (0 == poly->next)
	{
		poly->next = MakeListNode(node->coeff, node->expo);
	}
	else
	{
		poly->next->coeff += node->coeff;
	}

	return;
}

ListPoly MakeListPolyFromArrayPoly(const ArrayPoly p)
{
    assert (p != 0);

    ListNode *l, *h = (ListNode *)malloc(sizeof(ListNode));
    if (h)
    {
        l = h;
        for (int i = 0; i <= p->power; i++)
        {
            if (p->coeff[i] != 0)
            {
                ListNode *tmp = MakeListNode(p->coeff[i], i);
                assert(tmp);

                l->next = tmp;
                l = tmp;
            }
        }
    }

    return h;
}

void DestoryListPoly(ListPoly p)
{

}

void PrintListPoly(const ListPoly poly)
{
    assert(poly);

    ListNode *p = poly->next;   //with head
    if (p)
    {
        printf("\n");
        while (p->next)
        {
            if (p->expo == 0)
            {
                printf("%d + ", p->coeff);
            }
            else
            {
                printf("%dx(%d) + ", p->coeff, p->expo);
            }
            p = p->next;
        }
    }

    printf("%dx(%d)", p->coeff, p->expo);
}

ListPoly AddListPoly(const ListPoly poly1, const ListPoly poly2)
{
    assert(poly1 != 0 && poly2 != 0);

    ListNode *p1 = poly1->next;
    ListNode *p2 = poly2->next;

    ListNode *l, *tmp;
    ListNode *h = (ListNode *)malloc(sizeof(ListNode));
    if (h)
    {
        h->next = 0;
        l = h;

        while (p1 && p2)
        {
            if (p1->expo < p2->expo)
            {
                tmp = MakeListNode(p1->coeff, p1->expo);
                p1 = p1->next;
            }
            else if (p1->expo > p2->expo)
            {
                tmp = MakeListNode(p2->coeff, p2->expo);
                p2 = p2->next;
            }
            else
            {
                tmp = MakeListNode(p1->coeff + p2->coeff, p1->expo);
                p1 = p1->next;
                p2 = p2->next;
            }

            l->next = tmp;
            l = tmp;
        }

        while (p1)
        {
            tmp = MakeListNode(p1->coeff, p1->expo);
            l->next = tmp;
            l = tmp;
        }

        while (p2)
        {
            tmp = MakeListNode(p2->coeff, p2->expo);
            l->next = tmp;
            l = tmp;
        }
    }

    return h;
}

ListPoly MultiListPoly(const ListPoly poly1, const ListPoly poly2)
{
	assert(poly1 != 0 && poly2 != 0);

	ListPoly p1, p2;
	ListPoly value = MakeListNode(0, 0);

	ListNode data;
	
	for (p1 = poly1->next; p1; p1 = p1->next)
	{
		for (p2 = poly2->next; p2; p2 = p2->next)
		{
			ListNode* p = SetNodeValue(&data, p1->coeff * p2->coeff, p1->expo + p2->expo);
			AppendNodeInSort(value, p);
		}
	}
	
    return value;
}

